package 普通数组.缺失的第一个正数;

/**
 * 题目描述：
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。、
 * 输入：nums = [1,2,0]
 * 输出：3
 * 解释：范围 [1,2] 中的数字都在数组中。
 * 力扣：https://leetcode-cn.com/problems/first-missing-positive/
 * 力扣第41
 * */
/**
 * 题目思路：
 * 将数组本生当成哈希表来使用
 * 首先重拍数组，把每个正数放在对的地方
 * 就像4对应的索引就是3所以要放到3
 * 然后遍历重排后的数组不满足的不就是那个缺失的数组
 * */

class Solution1 {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 将每个数组放到正确的位置上
        for(int i = 0;i < n;i++){
            // 只处理正整数 只处理范围在1~n的数 当前数字不在正确位置上
            // 正确位置 nums[i] -1 正整数值-1就是他的索引
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                // 交换nums[i]和nums[nums[i] - 1]
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        // 寻找第一个不满足条件的位置
        for(int i = 0;i < n;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        // 如果所有位置都瞒足条件，则返回n+1
        return n + 1;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1,2,0};
        int[] nums2 = {3,4,-1,1};
        int[] nums3 = {7,8,9,11,12};
        int res1 = solution.firstMissingPositive(nums1);
        int res2 = solution.firstMissingPositive(nums2);
        int res3 = solution.firstMissingPositive(nums3);
        System.out.println(res1);
        System.out.println(res2);
        System.out.println(res3);
    }
}